package seelction;

/**
 * Created by mHandler on 2018/8/5 0005.
 * Description:
 */
public class OwnQuick3ways {
    private OwnQuick3ways() {
    }

    private static void sort(Comparable[] arr, int l, int r) {
        if (r <= 15) {
            InsertionSort.sort(arr, l, r);
        }
        swap(arr, l, (int) (Math.random() * (r - l + 1)) + l);
        Comparable v = arr[l];
        int lt = l, i = l + 1, gt = r + 1;
        while (i < gt) {
            if (arr[i].compareTo(v) < 0) {
                swap(arr, i, lt + 1);
                lt++;
                i++;
            } else if (arr[i].compareTo(v) > 0) {
                swap(arr, i, gt - 1);
                gt--;
            } else {
                i++;
            }
        }
        swap(arr, l, lt);
        sort(arr, l, lt - 1);
        sort(arr, gt, r);
    }

    public static void sort(Integer[] arr) {

        int n = arr.length;
        sort(arr, 0, n - 1);
    }

    private static void swap(Object[] arr, int l, int r) {
        Object temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }

    public static void main(String[] args) {
        int N = 1000000;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 10000);
        // SortTestHelper.testSort("seelction.OwnQuick3ways", arr);
        long start = System.currentTimeMillis();
        sort(arr, 0, arr.length - 1);
        System.out.println("排序花费：" + (System.currentTimeMillis() - start));

        return;
    }
}
